package com.example.demo.LeetCode精选TOP面试题;

/**
 * @author：zzc
 * @date: 2022/4/17
 */
public class 两数相加 {

    //给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
    //
    //请你将两个数相加，并以相同形式返回一个表示和的链表。
    //
    //你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
    //示例 1：
    //
    //输入：l1 = [2,4,3], l2 = [5,6,4]
    //输出：[7,0,8]
    //解释：342 + 465 = 807.
    //示例 2：
    //
    //输入：l1 = [0], l2 = [0]
    //输出：[0]
    //示例 3：
    //
    //输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
    //输出：[8,9,9,9,0,0,0,1]
    // 
    //
    //提示：
    //
    //每个链表中的节点数在范围 [1, 100] 内
    //0 <= Node.val <= 9
    //题目数据保证列表表示的数字不含前导零

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */

    public class ListNode {

        int val;
        ListNode next;

        public ListNode() {
        }

        public ListNode(int val) {
            this.val = val;
        }

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //l1遍历第一个 l2遍历第二个
        ListNode cur1 = l1,cur2=l2;
        //新建一个空的头指针
        ListNode head = new ListNode();
        //cur指针始终指向当前链表的最后一个节点
        ListNode cur = head;
        //carry表示每次加法后，应当进位的数
        int carry=0;
        while (cur1 != null || cur2 != null || carry != 0) {
            int first = cur1 == null ? 0 : cur1.val;
            int second = cur2 == null ? 0 : cur2.val;
            int sum = first + second + carry;
            ListNode temp = new ListNode(sum % 10);
            cur.next = temp;
            cur = cur.next;
            carry = sum / 10;

            //条件
            if (cur1 != null) {
                cur1 = cur1.next;
            }
            if (cur2 != null) {
                cur2 = cur2.next;
            }
        }
        return head.next;
    }

    public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        return add(l1, l2, 0);
    }

    /**
     返回两个链表相加的头部
     */
    public ListNode add(ListNode l1, ListNode l2, int bit) {
        if (l1 == null && l2 == null && bit == 0) {
            return null;
        }
        int val = bit;
        if (l1 != null) {
            val += l1.val;
            l1 = l1.next;
        }
        if (l2 != null) {
            val += l2.val;
            l2 = l2.next;
        }
        ListNode node = new ListNode(val % 10);
        node.next = add(l1, l2, val / 10);
        return node;
    }



































}
